import java.util.Arrays;

/**
* @description: 1928. 规定时间内到达终点的最小花费
* @author hewei
* @date 2022/8/24 15:44
* @version 1.0
*/

public class MinCost {

    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        int[][] dp = new int[maxTime + 1][n];
        for (int i = 0; i < maxTime + 1; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        for (int i = 1; i < maxTime + 1; i++) {
            for (int[] edge : edges) {
                int a = edge[0], b = edge[1], c = edge[2];
                if (dp[i - 1][a] != Integer.MAX_VALUE && c + i - 1 <= maxTime )
                    dp[c + i - 1][b] = Math.min(dp[c + i - 1][b], dp[i - 1][a] + passingFees[b]);
                if (dp[i - 1][b] != Integer.MAX_VALUE && c + i - 1 <= maxTime)
                    dp[c + i - 1][a] = Math.min(dp[c + i - 1][a], dp[i - 1][b] + passingFees[a]);
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < maxTime + 1; i++) {
            ans = Math.min(ans, dp[i][n - 1]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans + passingFees[0];
    }
}
